#include <iostream>
#include <string>
#include <cassert>
#include <fstream>
#include "arraylist.h"

using namespace std;

class Transition
{
	private:
		int srcState;
		char symbol;
		int dstState;
	
	public:
		
		Transition() : srcState(0), symbol(' '), dstState(0) {}
		Transition(int src, char sym, int dst) : srcState(src), symbol(sym), dstState(dst) {}
		
		int Src() const {return srcState;}
		char Sym() const {return symbol;}
		int Dst() const {return dstState;}
		
		void input(istream& in);
		void output(ostream& out) const;
};

void Transition::input(istream& in)
{
	char c;
	in >> c;
	assert(c == '(');
	in >> srcState;
	in >> c;
	assert(c == ',');
	in >> symbol;
	in >> c;
	assert(c == ',');
	in >> dstState;
	in >> c;
	assert(c == ')');
	return;
}

void Transition::output(ostream& out) const
{
	out << '{' << srcState << ", " << symbol << ", " << dstState << '}';
	return;
}

istream& operator>>(istream& in, Transition& t);

istream& operator>>(istream& in, Transition& t)
{
	t.input(in);
	return in;
}

ostream& operator<<(ostream& out, const Transition& t);

ostream& operator<<(ostream& out, const Transition& t)
{
	t.output(out);
	return out;
}

int findTransition(int currState, char currSymbol, ArrayList<Transition>& delta);

int main()
{
	ArrayList<Transition> delta;
	ArrayList<int> final;
	
//	Read the DFA from the file machine.txt

	cout << "Enter the DFA file name: ";
	string fileName;
	cin >> fileName;
	fstream fin(("C:/Documents and Settings/rkoether/My Documents/Classes/Coms 461/Homework/Fall 2004/ramosj/" + fileName).c_str());
	if (!fin)
	{
		cerr << "Failed to open " << fileName << endl;
		exit(1);
	}
	
	fin >> delta;
	fin >> final;
	
//	Process the string on the input tape

	int currState = 0;
	char currSymbol;
	bool rejected = false;
	
	cout << "Enter the input string: ";
	
	while (!rejected && cin >> currSymbol)
	{
		int next = findTransition(currState, currSymbol, delta);
		if (next == -1)
			rejected = true;
		else
			currState = next;
	}
	
	if (!rejected && final.Search(currState) > 0)
		cout << "The string is accepted" << endl;
	else
		cout << "The string is rejected" << endl;
	
	return 0;
}

int findTransition(int currState, char currSymbol, ArrayList<Transition>& delta)
{
	for (int i = 1; i <= delta.Size(); i++)
		if (delta[i].Src() == currState && delta[i].Sym() == currSymbol)
		{
			cout << "Read " << currSymbol << "; move from state " << currState
				 << " to state " << delta[i].Dst() << endl;
			return delta[i].Dst();
		}

	cout << "Read " << currSymbol << "; move from state " << currState
		 << " to the implicit reject state " << endl;
	return -1;
}